◀ Prev · Parts · Full · Next ▶

The fractional configuration LP of bin-packing It is the linear programming relaxation of the above ILP. It replaces the last constraint x c ∈ ∈ { 0 , … … , n } {\displaystyle x_{c}\in \{0,\ldots ,n\}} with the constraint x c ≥ ≥ 0 {\displaystyle x_{c}\geq 0} . In other words, each configuration can be used a fractional number of times. The relaxation was first presented by Gilmore and Gomory,cite-ref-gilmore61-2-1[2] and it is often called the Gilmore-Gomory linear program.cite-ref-22-8-0[8]

• Example: suppose there are 31 items of size 3 and 7 items of size 4, and the bin-size is 10. The configurations are: 4, 44, 34, 334, 3, 33, 333. The constraints are [0,0,1,2,1,2,3]*x=31 and [1,2,1,1,0,0,0]*x=7. An optimal solution to the fractional LP is [0,0,0,7,0,0,17/3] That is: there are 7 bins of configuration 334 and 17/3 bins of configuration 333. Note that only two different configurations are needed.

In short, the fractional LP can be written as follows:

minimize 1 ⋅ ⋅ x {\displaystyle ~\mathbf {1} \cdot \mathbf {x} ~} s.t. A x ≥ ≥ n {\displaystyle ~\mathbf {A} \mathbf {x} \geq \mathbf {n} ~} and x ≥ ≥ 0 {\displaystyle ~\mathbf {x} \geq 0~}

Where 1 is the vector (1,...,1) of size C, A is an S-by-C matrix in which each column represents a single configuration, and n is the vector (n1,...,nS).

◀ Prev · Parts · Full · Next ▶